#pragma once
#include <iostream>
#include <assert.h>

namespace AVLTree
{
	template<class K,class V>
	struct TreeNode
	{
		TreeNode<K, V>*  _left;     // 左子树
		TreeNode<K, V>*  _right;	// 右子树
		TreeNode<K, V>*  _parent;   // 父节点
		std::pair<K, V>  _val;      // 节点键值对(节点值)
		int              _bf;	    // 平衡因子

		TreeNode()
			:_left  (nullptr)
			,_right (nullptr)
			,_parent(nullptr)
			,_val(pair<K,V>())
			,_bf(0)
		{}

		TreeNode(const pair<K,V>& val)
			:_left   (nullptr)
			, _right (nullptr)
			, _parent(nullptr)
			, _val(val)
			, _bf(0)
		{}

		TreeNode(const K& key,const V& val)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _val({key,val})
			, _bf(0)
		{}
	};

	template<class T>
	struct less { bool operator()(const T& left, const T& right) { return left < right; } };
	template<class T>
	struct greater { bool operator()(const T& left, const T& right) { return left > right; } };


	// _bf
	// 右子树高度减去左子树高度  :  0 平衡  1 右边多一个 -1 左边多一个 
	template<class K,class V,class Compare = less<K>>
	class AVLTree
	{
		typedef std::pair<K, V> val_type;
		typedef TreeNode<K,V> Node;
	public:
		AVLTree():_root(nullptr),_size(0) {}

		pair<val_type,bool> insert(const val_type& data)
		{
			if (nullptr == _root)
			{
				Node* newnode = new Node(data);
				_root = newnode;
				++_size;
				return {data,true};
			}
			
			Node* newnode = new Node(data);
			Node* parent = _root;
			Node* cur = _root;
			while (cur)
			{
				if (_com(data.first, cur->_val.first))      // <
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (_com(cur->_val.first, data.first)) // >
				{
					parent = cur;
					cur = cur->_right;
				}
				else return { data,false };      // ==
			}

			if (_com(data.first, parent->_val.first)) parent->_left = newnode;
			else parent->_right = newnode;
			newnode->_parent = parent;
			cur = newnode;

			while (parent)
			{
				     if (parent->_left  == cur) --(parent->_bf);
				else if (parent->_right == cur) ++(parent->_bf);

				if (parent->_bf == 1 || parent->_bf == -1)
				{
					parent = parent->_parent;
					cur = cur->_parent;
				}
				else if (parent->_bf == 0) break;
				else //开始调整和旋转
				{
					if (parent->_bf == -2 && cur->_bf == -1) RotateR(parent);    //右单旋
					else if (parent->_bf == 2 && cur->_bf == 1) RotateL(parent); //左单旋
					else if (parent->_bf == -2 && cur->_bf == 1) RotateLR(parent); //左右旋
					else if (parent->_bf == 2 && cur->_bf == -1) RotateRL(parent); //右左旋
					else { assert(false); }
				}
			}
			++_size;
			return { data,true };
		}

		//检查AVL树合法性
		bool isAVL() { return _isAVL(_root); }

		//获取AVL树高度
		int getHigh() { return _getHigh(_root); }

		~AVLTree()
		{
            if(_root) DelTree(_root);
			_size = 0;
			_root = nullptr;
		}
	private:
		void DelTree(Node* root)
		{
			if (root->_left) DelTree(root->_left);
			if(root->_right) DelTree(root->_right);
			delete root;
		}

		//右单旋
		void RotateR(Node* parent)
		{
			Node* childL = parent->_left;
			Node* childLL = childL->_left;
			Node* childLR = childL->_right;
			Node* pparent = parent->_parent;

			parent->_left = childLR;
			if (childLR) childLR->_parent = parent;
			childL->_right = parent;
			parent->_parent = childL;

			if (pparent == nullptr)
			{
				_root = childL;
				_root->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent) pparent->_left = childL;
				else pparent->_right = childL;

				childL->_parent = pparent;
			}
			parent->_bf = childL->_bf = 0;
		}

		//左单旋
		void RotateL(Node* parent)
		{
			Node* childR = parent->_right;
			Node* childRL = childR->_left;
			Node* childRR = childR->_right;
			Node* pparent = parent->_parent;

			parent->_right = childRL;
			if (childRL) childRL->_parent = parent;
			childR->_left = parent;
			parent->_parent = childR;

			if (pparent == nullptr)
			{
				_root = childR;
				_root->_parent = nullptr;
			}
			else
			{
				if (pparent->_left == parent) pparent->_left = childR;
				else pparent->_right = childR;

				childR->_parent = pparent;
			}
			parent->_bf = childR->_bf = 0;
		}

		//左右双旋
		void RotateLR(Node* parent)
		{
			Node* childL  = parent->_left;
			Node* childLR = childL->_right;
			int bf = childLR->_bf;

			RotateL(childL);
			RotateR(parent);

			/*
						A
					B		C
				D		E
					  F
			*/
			if (bf == -1)
			{
				childL->_bf = 0;
				childLR->_bf = 0;
				parent->_bf = 1;
			}
			/*
						A
				   B		 C
				D	  E
						F
			*/
			else if (bf == 1)
			{
				childL->_bf = -1;
				childLR->_bf = 0;
				parent->_bf = 0;
			}
			/*
			*	   A
			*	B
			*	  C
			*/
			else if (bf == 0)
			{
				childL->_bf = 0;
				childLR->_bf = 0;
				parent->_bf = 0;
			}
			//如果出现其他情况，则表示代码有问题，需要检查
			else assert(false);
		}

		//右左双旋
		void RotateRL(Node* parent)
		{
			Node* childR  = parent->_right;
			Node* childRL = childR->_left;
			int bf = childRL->_bf;

			RotateR(childR);
			RotateL(parent);

			/*
					  A
				 B         C
				        D
					  E
			*/
			if (bf == -1)
			{
				parent->_bf = 0;
				childR->_bf = 1;
				childRL->_bf = 0;
			}
			/*
					  A
				 B         C
						D
					     E
			*/
			else if (bf == 1)
			{
				parent->_bf = -1;
				childR->_bf = 0;
				childRL->_bf = 0;
			}
			/*
				    A
					  B
					 C
			*/
			else if (bf == 0)
			{
				parent->_bf = 0;
				childR->_bf = 0;
				childRL->_bf = 0;
			}
			//如果出现其他情况，则表示代码有问题，需要检查
			else assert(false);
		}

		//检查AVL树合法性
		bool _isAVL(Node* root)
		{
			if (root == nullptr) return true;
			//获取左右子树高度
			int left  = _getHigh(root->_left);
			int right = _getHigh(root->_right);
			//如果右子树减左子树高度差的绝对值小于1 且差值与根的平衡因子相等 就继续检查子树
			if (abs(right - left) <= 1 && (right - left) == root->_bf) return true && _isAVL(root->_left) && _isAVL(root->_right);
			return false;
		}

		//获取树的深度
		int _getHigh(Node* root)
		{
			if (root == nullptr) return 0;
			int left  = _getHigh(root->_left);
			int right = _getHigh(root->_right);
			return 1+(left>=right ?left:right);
		}
	private:
		Node* _root;
		size_t _size;
		Compare _com;
	};

}















